#include<iostream>
using namespace std;
#include<vector>


struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return f2(head);
    }

    //头插法创建新链表
    ListNode* f1(ListNode* head) {
        ListNode* rhead = new ListNode();
        ListNode* rheadNext = rhead->next;
        while(head != nullptr) {
            cout << "insert:" << head->val << endl;
            ListNode* node = new ListNode(head->val,rheadNext);
            rhead->next = node;
            rheadNext = node;
            head = head->next;
        }
        delete rhead;

        return rheadNext;
    }

    //反转链表
    ListNode* f2(ListNode* head) {
        ListNode* curp = head;
        ListNode* prep = nullptr;
        while(head) {
            head = head->next;
            //反转
            curp->next = prep;
            //更新反转节点
            prep = curp;
            curp = head;
        }
        // printList(prep);
        return prep;
    }

    void test() {
        ListNode* head = createList();        
        printList(head);
        ListNode* rhead = reverseList(head);
        printList(rhead);
        // destroyList(&head);
        destroyList(&rhead);
    }

    ListNode* createList() {
        ListNode* curhead = new ListNode();
        ListNode* tem = curhead;

        vector<int> v = {1,2,3,4};
        for(auto it = v.begin(); it != v.end(); it++) {
            ListNode* node = new ListNode(*it);
            tem->next = node;
            tem = node;
        }

        ListNode* toFree = curhead;
        curhead = curhead->next;
        if(toFree) {
            delete toFree;
            toFree = nullptr;
        }
        return curhead;
    }

    void destroyList(ListNode** head) {
        ListNode* cur_node = *head;
        ListNode* next_node = (*head)->next;
        while(cur_node) {
            next_node = cur_node->next;
            delete cur_node;
            cur_node = next_node;
        }
    }

    void printList(ListNode* head) {
        while(head) {
            cout << head->val << " ";
            head = head->next;
        }
        cout << endl;
    } 
};

int main() {
    Solution().test();
}   
